Educational Codeforces Round 109 (Div. 2) D Armchairs
人が座っている椅子と座っていない椅子(空き椅子)の位置を持った数列について考える. 以後, 人が座っている椅子の位置を持った数列を$ A, その長さを$ s, 人が座っていない椅子の位置を持った数列を$ B, その長さを$ tとおく.
ここで, 人が座っている椅子について, 前から順にその人が次に座る椅子を決めていくことにする(条件よりそのような空き椅子は存在することが保証されている). すると, 次のようなDPをすることができる.
$ dp_{i, j} := $ i番目の人の移動まで決めて, $ j番目の空き椅子まで使うか使わないか決めたときのスコアの最小値 とすると, $ dp_{i + 1, j + 1} = dp_{i, j} + |A_i - A_j|(使う), dp_{i, j + 1} = dp_{i, j}(使わない)のように遷移でき, 答えを求めることができる.
よってこの問題を$ O(n^2)で解くことができた.